# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        pp = self.getParent(root, p)
        qp = self.getParent(root, q)
        for i in range(min(len(pp), len(qp))):
            if pp[i] != qp[i]:
                return qp[i - 1]
        if len(pp) < len(qp):
            return pp[-1]
        return qp[-1]

    def getParent(self, root: TreeNode, node):
        if root is None:
            return None
        if root == node:
            return [root]
        result = self.getParent(root.left, node)
        if result is None:
            result = self.getParent(root.right, node)
        if result:
            result.insert(0, root)
            return result
        return None


if __name__ == '__main__':
    so = Solution()
    s = [1, 0, 3, 4, 0, 1]
    r = so.isPalindrome(s)
    print(r)
